import bisect
from typing import List


class Solution:
    """
    方法： minSubArrayLen

    逻辑: 使用滑动窗口法从左到右遍历数组，记录当前窗口内的元素和。窗口内的元素和大于或等于目标值时，尝试缩小窗口左边界以找到最小的子数组长度。

    Args:
        target (int): 目标值，表示子数组的最小和。
        nums (List[int]): 一个整数数组，表示子数组的元素。

    Returns:
        int: 最小子数组的长度，如果不存在满足条件的子数组，则返回0。

    Time: O(n), n为nums数组的长度。

    Space: O(1), 只使用了常量级的额外空间。
    """
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        ans = n + 1
        s, left = 0, 0
        for right, x in enumerate(nums):
            s += x
            while s >= target:  #满足需求
                ans = min(ans, right - left +1)
                s -= nums[left]
                left += 1
        return ans if ans <= n else 0

    """
    方法： minSubArrayLen1

    逻辑: 使用前缀和数组和二分查找来找到最小子数组的长度。首先计算前缀和数组，接着对于每个可能的子数组起点，使用二分查找找到第一个大于或等于目标值的前缀和的位置，计算子数组的长度，并更新答案。

    Args:
        target (int): 目标值，表示子数组的最小和。
        nums (List[int]): 一个整数数组，表示子数组的元素。

    Returns:
        int: 最小子数组的长度，如果不存在满足条件的子数组，则返回0。

    Time: O(n log n), n为nums数组的长度。时间复杂度主要来自于计算前缀和数组和二分查找的操作。

    Space: O(n), 需要额外的空间来存储前缀和数组。
    """
    def minSubArrayLen1(self, target: int, nums: List[int]) -> int:
        if not nums: return 0
        n = len(nums)
        ans = n + 1
        sums = [0]
        for i in range(n):
            sums.append(sums[-1] + nums[i])
        for i in range(1, n + 1):
            s = target + sums[i - 1]
            bound = bisect.bisect_left(sums, s)
            if bound != len(sums):
                ans = min(ans, bound - (i - 1))
        return 0 if ans == n + 1 else ans

        